#pragma once
#include <vector>
using namespace std;

namespace ouyang
{
	template<class T>
	struct less
	{
		bool operator()(const T& left, const T& right)
		{
			return left < right;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& left, const T& right)
		{
			return left > right;
		}
	};

	template<class T, class Container = std::vector<T>, class Compare = less<T>>
	class Priority_queue
	{
	public:
		Priority_queue() :_c() {};

		template<class Iterator>
		Priority_queue(Iterator first, Iterator last)
			:_c(first, last)
		{
			int root = (_c.size() - 2) >> 1;
			for (; root >= 0; --root)
			{
				AdjustDown(root);
			}
		}

		void push(const T& val)
		{
			_c.push_back(val);
			AdjustUp(_c.size() - 1);
		}

		void pop()
		{
			if (empty())
				return;
			swap(_c.front(), _c.back());
			_c.pop_back();
			AdjustDown(0);
		}

		size_t size() const { return _c.size(); }
		bool empty() const { return _c.empty(); }

		const T& top() const { return _c.front(); }

	private:
		void AdjustUp(int child)
		{
			int parent = (child - 1) >> 1;
			while (child)
			{
				if (Compare()(_c[parent], _c[child]))
				{
					swap(_c[parent], _c[child]);
					child = parent;
					parent = (child - 1) >> 1;
				}
				else {
					break;
				}
			}
		}

		void AdjustDown(int parent)
		{
			int child = parent * 2 + 1;
			while (child < _c.size())
			{
				if (child + 1 < _c.size() && Compare()(_c[child], _c[child + 1]))
				{
					child += 1;
				}
				if (Compare()(_c[parent], _c[child]))
				{
					swap(_c[parent], _c[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else {
					break;
				}
			}
		}

		Container _c;
	};

}